package com.qt.bilibili.sort;

import java.util.Arrays;
import java.util.Random;

public class SortBj {

    public static void main(String[] args) {

        int[] arr = new int[10000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt();
        }

        long start = System.currentTimeMillis();
        //xzSort(arr);//选择排序 （卡死） 比冒泡快一点
        mpSort(arr);//冒泡排序（卡死）
        //czSort(arr);//插值排序--187308--187秒
        //kpSort(arr,0,arr.length - 1);//283毫秒
        long end =  System.currentTimeMillis();
        System.out.println(end - start);



    }

    public static void xzSort(int[] arr){

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }



    }

    public static void mpSort(int[] arr){

        //第几次冒泡
        for (int i = 0; i < arr.length; i++) {
            //比大小冒泡
            for (int j = i; j < arr.length - 1 - i; j++) {
                if(arr[j] < arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        //System.out.println(Arrays.toString(arr));


    }

    public static void czSort(int[] arr){

        //1.确定开始无序数据的索引
        int startIndex = -1;
        for (int i = 0 + 1; i < arr.length; i++) {
            if(arr[i] < arr[i - 1]){
                startIndex = i;
                break;
            }
        }

        //循环遍历剩下无序的部分
        for (int i = startIndex; i < arr.length; i++) {
            //记录开始索引
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]){
                //交换位置
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }



    }

    public static void kpSort(int[] arr,int i,int j){
        //快速排序
        int start = i;
        int end = j;

        //递归出口
        if(start > end){
            return;
        }

        //获取基准数
        int baseNumber = arr[i];
        //利用循环找到要交换数据的位置
        while (start != end){
            //大于的部分向前找
            while (true){
                if(arr[end] < baseNumber || end <= start){
                    break;
                }
                end--;
            }
            while (true){
                if(arr[start] > baseNumber || end <= start){
                    break;
                }
                start++;
            }
            //数据交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

        }
        //基数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        //确定左边范围
        kpSort(arr,i,start - 1);
        //确定右边范围
        kpSort(arr,start + 1,j);

    }




}
